Using Head and Tail we can get at the beginning of any non-empty list,
but in general we need more information than that. Rather than write
a whole bunch of recursive functions on lists, I'll implement two
fairly general functions, with which we can implement (almost) everything
else.
Foldl and Foldr both take in functions and apply them recursively
to a list. Foldl starts at the left of the list, and Foldr
starts at the right. For example,
#math131#
| Foldl~f~e~[1, 2, 3] |
= |
f~(f~(f~e~1)~2)~3 |
|
| Foldr~f~e~[1, 2, 3] |
= |
f~1~(f~2~(f~3~e)) |
|
These functions will be used a lot later on. Foldl can be defined:
#math132#
| Foldl~f~e~xs |
= |
xs~(Foldl'~f~e)~e |
|
| Foldl'~f~e~x~xs |
= |
Foldl~f~(f~e~x)~xs |
|
So #math133#Foldl~f~e~[ ] is
#math134#
| Foldl~f~e~Nil;SPMnbsp;;SPMnbsp;;SPMnbsp;;SPMnbsp; |
| |
= |
Nil~(Foldl'~f~e)~e |
|
| |
= |
#tex2html_wrap_indisplay2458#e#tex2html_wrap_indisplay2459#Foldl#tex2html_wrap_indisplay2460#@@ffe |
|
And #math135#Foldl~f~e~(x : xs) is
#math136#
| Foldl~f~e~(Cons~x~xs);SPMnbsp;;SPMnbsp;;SPMnbsp;;SPMnbsp; |
| |
= |
Cons~x~xs~(Foldl'~f~e)~e |
|
| |
= |
Foldl'~f~e~x~xs |
|
| |
= |
Foldl~f~(f~e~x)~xs |
|
For example, #math137#Foldl~f~e~[1, 2, 3] is
#math138#
| Foldl~f~e~[1, 2, 3];SPMnbsp;;SPMnbsp;;SPMnbsp;;SPMnbsp; |
| |
= |
Foldl~f~(f~e~1)~[2, 3] |
|
| |
= |
Foldl~f~(f~(f~e~1)~2)~[3] |
|
| |
= |
Foldl~f~(f~(f~(f~e~1)~2)~3)~[ ] |
|
| |
= |
f~(f~(f~e~1)~2)~3 |
|
as promised. Similarly, we can define Foldr as
#math139#
| Foldr~f~e~xs |
= |
xs~(Foldr'~f~e)~e |
|
| Foldr'~f~e~x~xs |
= |
f~x~(Foldr~f~e~xs) |
|
For Foldr~f to respect equality, f~x should respect equality.
When we do the unfolding, we discover that
#math140#
| Foldr~f~e~[ ] |
= |
e |
|
| Foldr~f~e~(x : xs) |
= |
f~e~(Foldr~f~e~xs) |
|
Foldr tends to be more efficient than Foldl, because Foldl
has to run along the entire list before it can start applying f,
whereas Foldr can apply f straight away. If f is a lazy function,
this can make quite a difference. Foldl on infinite lists, anyone?